package com.lw.leetcode.dp.c;

import com.lw.test.util.Utils;

/**
 * Created with IntelliJ IDEA.
 * 1416. 恢复数组
 *
 * @author liw
 * @version 1.0
 * @date 2022/10/27 17:30
 */
public class NumberOfArrays {

    public static void main(String[] args) {
        NumberOfArrays test = new NumberOfArrays();

        // 34
//        String str = "1234567890";
//        int k = 90;

        // 1
//        String str = "2020";
//        int k = 30;

        // 8
//        String str = "1317";
//        int k = 2000;

        // 0
//        String str = "1000";
//        int k = 10;

        // 1
//        String str = "1000";
//        int k = 1000;

        //
        String str = Utils.getStr(100000, '0', '9');
        int k = 1000000000;
        System.out.println(k);

        int i = test.numberOfArrays(str, k);
        System.out.println(i);
    }

    public int numberOfArrays(String s, int k) {
        char[] chars = s.toCharArray();
        if (chars[0] == '0') {
            return 0;
        }
        int length = s.length();
        long[] arr = new long[length];
        int l = String.valueOf(k).length();
        for (int i = 0; i < length; i++) {
            for (int j = Math.max(0, i - l + 1); j <= i; j++) {
                if (find(chars, j, i, k)) {
                    arr[i] += (j - 1 < 0 ? 1 : arr[j - 1]);
                }
            }
            arr[i] %= 1000000007;
        }
        return (int) arr[length - 1];
    }

    private boolean find(char[] chars, int st, int end, int k) {
        if (chars[st] == '0') {
            return false;
        }
        long l = 0;
        for (int i = st; i <= end; i++) {
            l = l * 10 + chars[i] - '0';
        }
        return l <= k;
    }

}
